package net.projecteuler.programs.program0005;

import net.projecteuler.programs.TimeLogger;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Smallest multiple
 *
 * 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
 *
 *  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
 * 
 * Created by zhaojjd on 2016/3/21.
 */
public class Program0005 {

    List<Integer> factors = new ArrayList<Integer>();

    private Map<Integer, Integer> getFactorMap(int num){
        Map<Integer, Integer> factorMap = new HashMap<Integer, Integer>();
        int len = factors.size();
        for(int i = 0; i < len; i++){
            int factor = factors.get(i);
            if(num % factor == 0){
                if(factorMap.containsKey(factor)){
                    factorMap.put(factor, factorMap.get(factor) + 1);
                }else {
                    factorMap.put(factor, 1);
                }
                i--;
                num /= factor;
                if(num == 1){
                    break;
                }
            }
        }
        if(num > 1){
            int base = factors.size() > 0 ? factors.get(factors.size() - 1) + 1 : 2;
            for (int i = base; i <= num; i++) {
                if(num % i == 0){
                    if(factorMap.containsKey(i)){
                        factorMap.put(i, factorMap.get(i) + 1);
                    }else {
                        factorMap.put(i, 1);
                    }
                    if(!factors.contains(i)){
                        factors.add(i);
                    }
                    num /= i;
                    i--;
                    if(num == 1){
                        break;
                    }
                }
            }
        }
        return factorMap;
    }

    public long LCM(){
        Map<Integer, Integer> rstmap = new HashMap<Integer, Integer>();
        for (int i = 2; i <= 20; i++) {
            Map<Integer, Integer> map = getFactorMap(i);
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                Integer key = entry.getKey();
                if(rstmap.get(key) == null){
                    rstmap.put(key, entry.getValue());
                }else if(entry.getValue() > rstmap.get(key)){
                    rstmap.put(key, entry.getValue());
                }
            }
        }

        long rst = 1;
        for (Map.Entry<Integer, Integer> entry : rstmap.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();

            rst *= Math.pow(key, value);
        }
        return rst;
    }


    //////////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * greatest common divisor
     */
    private long GCD(long s, long b) {
        // s-small,b-big
        if (s < b) {
            s += b;
            b = s - b;
            s -= b;
        }
        while (b != 0) {
            s = s % b + b;
            b = s - b;
            s = s - b;
        }
        return s;
    }

    /**
     * a lowest common multiple
     */
    private long LCM(long a, long b) {
        return a * b / GCD(a, b);
    }

    public long LCM2(){
        long rst = 2;
        for (int i = 20; i > 2; i--) {
            rst = LCM(rst, i);
        }
        return rst;
    }

    public static void main(String[] args) {
        Program0005 p = new Program0005();
        TimeLogger.tag();
        System.out.println("p.LCM() = " + p.LCM());
        TimeLogger.print();
        TimeLogger.tag();
        System.out.println("p.LCM2() = " + p.LCM2());
        TimeLogger.print();
    }

}
